#encoding = utf-8
"""
有5位同学，从左到右分别编号为0,1,2,3,4号。
0号手中有2块1元硬币，1号手中硬币数是0号的3倍，
依次类推，右侧是相邻左侧硬笔数的3倍，请问5号手中有多少硬币数？
第10号手中呢？

设 f(n) 为第n号手中硬币的数量, 求f(5) = ？
已知：
   f(1)=2,  f(2) = 3*f(1)=> f(n) =3*f(n-1)
"""
def f(n):
	if n==1:
		return 2
	else:
		return 3*f(n-1)



# 使用动态规划法优化递归程序，
# 重复利用已经计算的子结构结果
def fastFib(n,mem):
	if not n in mem.keys():
		mem[n] = 3*fastFib(n-1,mem)
	return mem[n]
def FibDP(n):
	mem = {1:2}
	return fastFib(n,mem)

x = FibDP(100)
print(x)